{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Gradient Checking\n",
    "\n",
    "欢迎来到本周的最后作业！在这个任务中，您将学会实现并使用梯度检测。\n",
    "\n",
    "您是一个在全球范围内开展移动支付的团队的一份子，并被要求建立一个深度学习模式来检测欺诈行为 -- 每当有人付款时，您想要查看付款是否有欺诈行为，例如用户帐户是否被黑客占用。\n",
    "\n",
    "这个模型的反向传播很复杂，又因为这个应用实在太重要，所以你被要求向你公司的CEO证明你的反向传播实际上是正确的！为了验证是否正确有效，你使用了“Gradient Checking”。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Packages\n",
    "import numpy as np\n",
    "from testCases import *\n",
    "from gc_utils import sigmoid, relu, dictionary_to_vector, vector_to_dictionary, gradients_to_vector"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1) How does gradient checking work?\n",
    "\n",
    "反向传播需要计算梯度 $\\frac{\\partial J}{\\partial \\theta}$,  其中$\\theta$ 表示模型的参数. $J$ 是使用前向传播和损失函数计算的.\n",
    "\n",
    "因为前向传播实现相对简单, 所以你确信 $J$ 计算正确. Thus, you can use your code for computing $J$ to verify the code for computing $\\frac{\\partial J}{\\partial \\theta}$. \n",
    "\n",
    "现在让我们回头来看一下导数（或者梯度）的定义：\n",
    "$$ \\frac{\\partial J}{\\partial \\theta} = \\lim_{\\varepsilon \\to 0} \\frac{J(\\theta + \\varepsilon) - J(\\theta - \\varepsilon)}{2 \\varepsilon} \\tag{1}$$\n",
    "\n",
    "If you're not familiar with the \"$\\displaystyle \\lim_{\\varepsilon \\to 0}$\" notation, it's just a way of saying \"when $\\varepsilon$ is really really small.\"\n",
    "\n",
    "我们知道以下几点：\n",
    "\n",
    "- $\\frac{\\partial J}{\\partial \\theta}$ 是你想去确保正确计算的东西. \n",
    "- You can compute $J(\\theta + \\varepsilon)$ and $J(\\theta - \\varepsilon)$ (in the case that $\\theta$ is a real number), since you're confident your implementation for $J$ is correct. \n",
    "\n",
    "让我们用公式（1）和一个较小的值 $\\varepsilon$ 让你的CEO相信你计算$\\frac{\\partial J}{\\partial \\theta}$的代码是正确的"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2) 1-dimensional gradient checking\n",
    "\n",
    "考虑一维线性函数 $J(\\theta) = \\theta x$. 该模型只包含一个实值参数 $\\theta$, 并采取 $x$ 作为输入。\n",
    "\n",
    "你将实现代码去计算 $J(.)$ 和它的导数 $\\frac{\\partial J}{\\partial \\theta}$. 然后你将使用“Gradient Checking”去确保你关于$J$ 的导数计算是正确的. \n",
    "\n",
    "<img src=\"images/1Dgrad_kiank.png\" style=\"width:600px;height:250px;\">\n",
    "<caption><center> <u> **Figure 1** </u>: **1D linear model**<br> </center></caption>\n",
    "\n",
    "上图显示了计算的关键步骤: First start with $x$, then evaluate the function $J(x)$ (\"forward propagation\"). Then compute the derivative $\\frac{\\partial J}{\\partial \\theta}$ (\"backward propagation\"). \n",
    "\n",
    "**Exercise**: 实现这个简单函数的前向传播和后向传播. I.e., compute both $J(.)$ (\"forward propagation\") and its derivative with respect to $\\theta$ (\"backward propagation\"), in two separate functions. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# GRADED FUNCTION: forward_propagation\n",
    "\n",
    "def forward_propagation(x, theta):\n",
    "    \"\"\"\n",
    "    Implement the linear forward propagation (compute J) presented in Figure 1 (J(theta) = theta * x)\n",
    "    \n",
    "    Arguments:\n",
    "    x -- a real-valued input\n",
    "    theta -- our parameter, a real number as well\n",
    "    \n",
    "    Returns:\n",
    "    J -- the value of function J, computed using the formula J(theta) = theta * x\n",
    "    \"\"\"\n",
    "    \n",
    "    ### START CODE HERE ### (approx. 1 line)\n",
    "    J = theta * x\n",
    "    ### END CODE HERE ###\n",
    "    \n",
    "    return J"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "J = 8\n"
     ]
    }
   ],
   "source": [
    "x, theta = 2, 4\n",
    "J = forward_propagation(x, theta)\n",
    "print (\"J = \" + str(J))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Expected Output**:\n",
    "\n",
    "<table style=>\n",
    "    <tr>\n",
    "        <td>  ** J **  </td>\n",
    "        <td> 8</td>\n",
    "    </tr>\n",
    "</table>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise**: Now, implement the backward propagation step (derivative computation) of Figure 1. That is, compute the derivative of $J(\\theta) = \\theta x$ with respect to $\\theta$. To save you from doing the calculus, you should get $dtheta = \\frac { \\partial J }{ \\partial \\theta} = x$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# GRADED FUNCTION: backward_propagation\n",
    "\n",
    "def backward_propagation(x, theta):\n",
    "    \"\"\"\n",
    "    Computes the derivative of J with respect to theta (see Figure 1).\n",
    "    \n",
    "    Arguments:\n",
    "    x -- a real-valued input\n",
    "    theta -- our parameter, a real number as well\n",
    "    \n",
    "    Returns:\n",
    "    dtheta -- the gradient of the cost with respect to theta\n",
    "    \"\"\"\n",
    "    \n",
    "    ### START CODE HERE ### (approx. 1 line)\n",
    "    dtheta = x\n",
    "    ### END CODE HERE ###\n",
    "    \n",
    "    return dtheta"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "dtheta = 2\n"
     ]
    }
   ],
   "source": [
    "x, theta = 2, 4\n",
    "dtheta = backward_propagation(x, theta)\n",
    "print (\"dtheta = \" + str(dtheta))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Expected Output**:\n",
    "\n",
    "<table>\n",
    "    <tr>\n",
    "        <td>  ** dtheta **  </td>\n",
    "        <td> 2 </td>\n",
    "    </tr>\n",
    "</table>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise**: To show that the `backward_propagation()` function is correctly computing the gradient $\\frac{\\partial J}{\\partial \\theta}$, let's implement gradient checking.\n",
    "\n",
    "**Instructions**:\n",
    "- First compute \"gradapprox\" using the formula above (1) and a small value of $\\varepsilon$. Here are the Steps to follow:\n",
    "    1. $\\theta^{+} = \\theta + \\varepsilon$\n",
    "    2. $\\theta^{-} = \\theta - \\varepsilon$\n",
    "    3. $J^{+} = J(\\theta^{+})$\n",
    "    4. $J^{-} = J(\\theta^{-})$\n",
    "    5. $gradapprox = \\frac{J^{+} - J^{-}}{2  \\varepsilon}$\n",
    "- Then compute the gradient using backward propagation, and store the result in a variable \"grad\"\n",
    "- Finally, compute the relative difference between \"gradapprox\" and the \"grad\" using the following formula:\n",
    "$$ difference = \\frac {\\mid\\mid grad - gradapprox \\mid\\mid_2}{\\mid\\mid grad \\mid\\mid_2 + \\mid\\mid gradapprox \\mid\\mid_2} \\tag{2}$$\n",
    "You will need 3 Steps to compute this formula:\n",
    "   - 1'. compute the numerator using np.linalg.norm(...)\n",
    "   - 2'. compute the denominator. You will need to call np.linalg.norm(...) twice.\n",
    "   - 3'. divide them.\n",
    "- If this difference is small (say less than $10^{-7}$), you can be quite confident that you have computed your gradient correctly. Otherwise, there may be a mistake in the gradient computation. \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# GRADED FUNCTION: gradient_check\n",
    "\n",
    "def gradient_check(x, theta, epsilon = 1e-7):\n",
    "    \"\"\"\n",
    "    Implement the backward propagation presented in Figure 1.\n",
    "    \n",
    "    Arguments:\n",
    "    x -- a real-valued input\n",
    "    theta -- our parameter, a real number as well\n",
    "    epsilon -- tiny shift to the input to compute approximated gradient with formula(1)\n",
    "    \n",
    "    Returns:\n",
    "    difference -- difference (2) between the approximated gradient and the backward propagation gradient\n",
    "    \"\"\"\n",
    "    \n",
    "    # Compute gradapprox using left side of formula (1). epsilon is small enough, you don't need to worry about the limit.\n",
    "    ### START CODE HERE ### (approx. 5 lines)\n",
    "    thetaplus = theta + epsilon                           # Step 1\n",
    "    thetaminus = theta - epsilon                          # Step 2\n",
    "    J_plus = thetaplus * x                                # Step 3\n",
    "    J_minus = thetaminus * x                              # Step 4\n",
    "    gradapprox = (J_plus - J_minus)/(2 * epsilon)         # Step 5\n",
    "    ### END CODE HERE ###\n",
    "    \n",
    "    # Check if gradapprox is close enough to the output of backward_propagation()\n",
    "    ### START CODE HERE ### (approx. 1 line)\n",
    "    grad = backward_propagation(x, theta)\n",
    "    ### END CODE HERE ###\n",
    "    \n",
    "    ### START CODE HERE ### (approx. 1 line)\n",
    "    numerator = np.linalg.norm(grad - gradapprox)                     # Step 1'\n",
    "    denominator = np.linalg.norm(grad) + np.linalg.norm(gradapprox)   # Step 2'\n",
    "    difference = numerator / denominator                              # Step 3'\n",
    "    ### END CODE HERE ###\n",
    "    \n",
    "    if difference < 1e-7:\n",
    "        print (\"The gradient is correct!\")\n",
    "    else:\n",
    "        print (\"The gradient is wrong!\")\n",
    "    \n",
    "    return difference"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The gradient is correct!\n",
      "difference = 2.91933588329e-10\n"
     ]
    }
   ],
   "source": [
    "x, theta = 2, 4\n",
    "difference = gradient_check(x, theta)\n",
    "print(\"difference = \" + str(difference))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Expected Output**:\n",
    "The gradient is correct!\n",
    "<table>\n",
    "    <tr>\n",
    "        <td>  ** difference **  </td>\n",
    "        <td> 2.9193358103083e-10 </td>\n",
    "    </tr>\n",
    "</table>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Congrats, the difference is smaller than the $10^{-7}$ threshold. So you can have high confidence that you've correctly computed the gradient in `backward_propagation()`. \n",
    "\n",
    "Now, in the more general case, your cost function $J$ has more than a single 1D input. When you are training a neural network, $\\theta$ actually consists of multiple matrices $W^{[l]}$ and biases $b^{[l]}$! It is important to know how to do a gradient check with higher-dimensional inputs. Let's do it!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3) N-dimensional gradient checking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "The following figure describes the forward and backward propagation of your fraud detection model.\n",
    "\n",
    "<img src=\"images/NDgrad_kiank.png\" style=\"width:600px;height:400px;\">\n",
    "<caption><center> <u> **Figure 2** </u>: **deep neural network**<br>*LINEAR -> RELU -> LINEAR -> RELU -> LINEAR -> SIGMOID*</center></caption>\n",
    "\n",
    "Let's look at your implementations for forward propagation and backward propagation. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def forward_propagation_n(X, Y, parameters):\n",
    "    \"\"\"\n",
    "    Implements the forward propagation (and computes the cost) presented in Figure 3.\n",
    "    \n",
    "    Arguments:\n",
    "    X -- training set for m examples\n",
    "    Y -- labels for m examples \n",
    "    parameters -- python dictionary containing your parameters \"W1\", \"b1\", \"W2\", \"b2\", \"W3\", \"b3\":\n",
    "                    W1 -- weight matrix of shape (5, 4)\n",
    "                    b1 -- bias vector of shape (5, 1)\n",
    "                    W2 -- weight matrix of shape (3, 5)\n",
    "                    b2 -- bias vector of shape (3, 1)\n",
    "                    W3 -- weight matrix of shape (1, 3)\n",
    "                    b3 -- bias vector of shape (1, 1)\n",
    "    \n",
    "    Returns:\n",
    "    cost -- the cost function (logistic cost for one example)\n",
    "    \"\"\"\n",
    "    \n",
    "    # retrieve parameters\n",
    "    m = X.shape[1]\n",
    "    W1 = parameters[\"W1\"]\n",
    "    b1 = parameters[\"b1\"]\n",
    "    W2 = parameters[\"W2\"]\n",
    "    b2 = parameters[\"b2\"]\n",
    "    W3 = parameters[\"W3\"]\n",
    "    b3 = parameters[\"b3\"]\n",
    "\n",
    "    # LINEAR -> RELU -> LINEAR -> RELU -> LINEAR -> SIGMOID\n",
    "    Z1 = np.dot(W1, X) + b1\n",
    "    A1 = relu(Z1)\n",
    "    Z2 = np.dot(W2, A1) + b2\n",
    "    A2 = relu(Z2)\n",
    "    Z3 = np.dot(W3, A2) + b3\n",
    "    A3 = sigmoid(Z3)\n",
    "\n",
    "    # Cost\n",
    "    logprobs = np.multiply(-np.log(A3),Y) + np.multiply(-np.log(1 - A3), 1 - Y)\n",
    "    cost = 1./m * np.sum(logprobs)\n",
    "    \n",
    "    cache = (Z1, A1, W1, b1, Z2, A2, W2, b2, Z3, A3, W3, b3)\n",
    "    \n",
    "    return cost, cache"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, run backward propagation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def backward_propagation_n(X, Y, cache):\n",
    "    \"\"\"\n",
    "    Implement the backward propagation presented in figure 2.\n",
    "    \n",
    "    Arguments:\n",
    "    X -- input datapoint, of shape (input size, 1)\n",
    "    Y -- true \"label\"\n",
    "    cache -- cache output from forward_propagation_n()\n",
    "    \n",
    "    Returns:\n",
    "    gradients -- A dictionary with the gradients of the cost with respect to each parameter, activation and pre-activation variables.\n",
    "    \"\"\"\n",
    "    \n",
    "    m = X.shape[1]\n",
    "    (Z1, A1, W1, b1, Z2, A2, W2, b2, Z3, A3, W3, b3) = cache\n",
    "    \n",
    "    dZ3 = A3 - Y\n",
    "    dW3 = 1./m * np.dot(dZ3, A2.T)\n",
    "    db3 = 1./m * np.sum(dZ3, axis=1, keepdims = True)\n",
    "    \n",
    "    dA2 = np.dot(W3.T, dZ3)\n",
    "    dZ2 = np.multiply(dA2, np.int64(A2 > 0))\n",
    "    dW2 = 1./m * np.dot(dZ2, A1.T) * 2\n",
    "    db2 = 1./m * np.sum(dZ2, axis=1, keepdims = True)\n",
    "    \n",
    "    dA1 = np.dot(W2.T, dZ2)\n",
    "    dZ1 = np.multiply(dA1, np.int64(A1 > 0))\n",
    "    dW1 = 1./m * np.dot(dZ1, X.T)\n",
    "    db1 = 4./m * np.sum(dZ1, axis=1, keepdims = True)\n",
    "    \n",
    "    gradients = {\"dZ3\": dZ3, \"dW3\": dW3, \"db3\": db3,\n",
    "                 \"dA2\": dA2, \"dZ2\": dZ2, \"dW2\": dW2, \"db2\": db2,\n",
    "                 \"dA1\": dA1, \"dZ1\": dZ1, \"dW1\": dW1, \"db1\": db1}\n",
    "    \n",
    "    return gradients"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "You obtained some results on the fraud detection test set but you are not 100% sure of your model. Nobody's perfect! Let's implement gradient checking to verify if your gradients are correct."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**How does gradient checking work?**.\n",
    "\n",
    "As in 1) and 2), you want to compare \"gradapprox\" to the gradient computed by backpropagation. The formula is still:\n",
    "\n",
    "$$ \\frac{\\partial J}{\\partial \\theta} = \\lim_{\\varepsilon \\to 0} \\frac{J(\\theta + \\varepsilon) - J(\\theta - \\varepsilon)}{2 \\varepsilon} \\tag{1}$$\n",
    "\n",
    "However, $\\theta$ is not a scalar anymore. It is a dictionary called \"parameters\". We implemented a function \"`dictionary_to_vector()`\" for you. It converts the \"parameters\" dictionary into a vector called \"values\", obtained by reshaping all parameters (W1, b1, W2, b2, W3, b3) into vectors and concatenating them.\n",
    "\n",
    "The inverse function is \"`vector_to_dictionary`\" which outputs back the \"parameters\" dictionary.\n",
    "\n",
    "<img src=\"images/dictionary_to_vector.png\" style=\"width:600px;height:400px;\">\n",
    "<caption><center> <u> **Figure 2** </u>: **dictionary_to_vector() and vector_to_dictionary()**<br> You will need these functions in gradient_check_n()</center></caption>\n",
    "\n",
    "We have also converted the \"gradients\" dictionary into a vector \"grad\" using gradients_to_vector(). You don't need to worry about that.\n",
    "\n",
    "**Exercise**: Implement gradient_check_n().\n",
    "\n",
    "**Instructions**: Here is pseudo-code that will help you implement the gradient check.\n",
    "\n",
    "For each i in num_parameters:\n",
    "- To compute `J_plus[i]`:\n",
    "    1. Set $\\theta^{+}$ to `np.copy(parameters_values)`\n",
    "    2. Set $\\theta^{+}_i$ to $\\theta^{+}_i + \\varepsilon$\n",
    "    3. Calculate $J^{+}_i$ using to `forward_propagation_n(x, y, vector_to_dictionary(`$\\theta^{+}$ `))`.     \n",
    "- To compute `J_minus[i]`: do the same thing with $\\theta^{-}$\n",
    "- Compute $gradapprox[i] = \\frac{J^{+}_i - J^{-}_i}{2 \\varepsilon}$\n",
    "\n",
    "Thus, you get a vector gradapprox, where gradapprox[i] is an approximation of the gradient with respect to `parameter_values[i]`. You can now compare this gradapprox vector to the gradients vector from backpropagation. Just like for the 1D case (Steps 1', 2', 3'), compute: \n",
    "$$ difference = \\frac {\\| grad - gradapprox \\|_2}{\\| grad \\|_2 + \\| gradapprox \\|_2 } \\tag{3}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# GRADED FUNCTION: gradient_check_n\n",
    "\n",
    "def gradient_check_n(parameters, gradients, X, Y, epsilon = 1e-7):\n",
    "    \"\"\"\n",
    "    Checks if backward_propagation_n computes correctly the gradient of the cost output by forward_propagation_n\n",
    "    \n",
    "    Arguments:\n",
    "    parameters -- python dictionary containing your parameters \"W1\", \"b1\", \"W2\", \"b2\", \"W3\", \"b3\":\n",
    "    grad -- output of backward_propagation_n, contains gradients of the cost with respect to the parameters. \n",
    "    x -- input datapoint, of shape (input size, 1)\n",
    "    y -- true \"label\"\n",
    "    epsilon -- tiny shift to the input to compute approximated gradient with formula(1)\n",
    "    \n",
    "    Returns:\n",
    "    difference -- difference (2) between the approximated gradient and the backward propagation gradient\n",
    "    \"\"\"\n",
    "    \n",
    "    # Set-up variables\n",
    "    parameters_values, _ = dictionary_to_vector(parameters)\n",
    "    grad = gradients_to_vector(gradients)\n",
    "    num_parameters = parameters_values.shape[0]\n",
    "    J_plus = np.zeros((num_parameters, 1))\n",
    "    J_minus = np.zeros((num_parameters, 1))\n",
    "    gradapprox = np.zeros((num_parameters, 1))\n",
    "    \n",
    "    # Compute gradapprox\n",
    "    for i in range(num_parameters):\n",
    "        \n",
    "        # Compute J_plus[i]. Inputs: \"parameters_values, epsilon\". Output = \"J_plus[i]\".\n",
    "        # \"_\" is used because the function you have to outputs two parameters but we only care about the first one\n",
    "        ### START CODE HERE ### (approx. 3 lines)\n",
    "        thetaplus = np.copy(parameters_values)                                         # Step 1\n",
    "        thetaplus[i][0] = thetaplus[i][0] + epsilon                                    # Step 2\n",
    "        J_plus[i], _ = forward_propagation_n(X, Y, vector_to_dictionary(thetaplus))    # Step 3\n",
    "        ### END CODE HERE ###\n",
    "        \n",
    "        # Compute J_minus[i]. Inputs: \"parameters_values, epsilon\". Output = \"J_minus[i]\".\n",
    "        ### START CODE HERE ### (approx. 3 lines)\n",
    "        thetaminus = np.copy(parameters_values)                                     # Step 1\n",
    "        thetaminus[i][0] = thetaminus[i][0] - epsilon                               # Step 2        \n",
    "        J_minus[i], _ = forward_propagation_n(X, Y, vector_to_dictionary(thetaminus))                                  # Step 3\n",
    "        ### END CODE HERE ###\n",
    "        \n",
    "        # Compute gradapprox[i]\n",
    "        ### START CODE HERE ### (approx. 1 line)\n",
    "        gradapprox[i] = (J_plus[i] - J_minus[i]) / (2 * epsilon)\n",
    "        ### END CODE HERE ###\n",
    "    \n",
    "    # Compare gradapprox to backward propagation gradients by computing difference.\n",
    "    ### START CODE HERE ### (approx. 1 line)\n",
    "    numerator = np.linalg.norm(gradapprox - grad)                                # Step 1'\n",
    "    denominator = np.linalg.norm(grad) + np.linalg.norm(gradapprox)              # Step 2'\n",
    "    difference = numerator / denominator                                         # Step 3'\n",
    "    ### END CODE HERE ###\n",
    "\n",
    "    if difference > 1e-7:\n",
    "        print (\"\\033[93m\" + \"There is a mistake in the backward propagation! difference = \" + str(difference) + \"\\033[0m\")\n",
    "    else:\n",
    "        print (\"\\033[92m\" + \"Your backward propagation works perfectly fine! difference = \" + str(difference) + \"\\033[0m\")\n",
    "    \n",
    "    return difference"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false,
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\u001b[93mThere is a mistake in the backward propagation! difference = 0.285093156776\u001b[0m\n"
     ]
    }
   ],
   "source": [
    "X, Y, parameters = gradient_check_n_test_case()\n",
    "\n",
    "cost, cache = forward_propagation_n(X, Y, parameters)\n",
    "gradients = backward_propagation_n(X, Y, cache)\n",
    "difference = gradient_check_n(parameters, gradients, X, Y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Expected output**:\n",
    "\n",
    "<table>\n",
    "    <tr>\n",
    "        <td>  ** There is a mistake in the backward propagation!**  </td>\n",
    "        <td> difference = 0.285093156781 </td>\n",
    "    </tr>\n",
    "</table>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It seems that there were errors in the `backward_propagation_n` code we gave you! Good that you've implemented the gradient check. Go back to `backward_propagation` and try to find/correct the errors *(Hint: check dW2 and db1)*. Rerun the gradient check when you think you've fixed it. Remember you'll need to re-execute the cell defining `backward_propagation_n()` if you modify the code. \n",
    "\n",
    "Can you get gradient check to declare your derivative computation correct? Even though this part of the assignment isn't graded, we strongly urge you to try to find the bug and re-run gradient check until you're convinced backprop is now correctly implemented. \n",
    "\n",
    "**Note** \n",
    "- Gradient Checking is slow! Approximating the gradient with $\\frac{\\partial J}{\\partial \\theta} \\approx  \\frac{J(\\theta + \\varepsilon) - J(\\theta - \\varepsilon)}{2 \\varepsilon}$ is computationally costly. For this reason, we don't run gradient checking at every iteration during training. Just a few times to check if the gradient is correct. \n",
    "- Gradient Checking, at least as we've presented it, doesn't work with dropout. You would usually run the gradient check algorithm without dropout to make sure your backprop is correct, then add dropout. \n",
    "\n",
    "Congrats, you can be confident that your deep learning model for fraud detection is working correctly! You can even use this to convince your CEO. :) \n",
    "\n",
    "<font color='blue'>\n",
    "**What you should remember from this notebook**:\n",
    "- Gradient checking verifies closeness between the gradients from backpropagation and the numerical approximation of the gradient (computed using forward propagation).\n",
    "- Gradient checking is slow, so we don't run it in every iteration of training. You would usually run it only to make sure your code is correct, then turn it off and use backprop for the actual learning process. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "coursera": {
   "course_slug": "deep-neural-network",
   "graded_item_id": "n6NBD",
   "launcher_item_id": "yfOsE"
  },
  "kernelspec": {
   "display_name": "Python [default]",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
